﻿/**
 * --------------------------------------
 * FileName: work.3.c
 * Content: 
 *      实现locate功能，根据查找频度重新安排
 *      元素位置。
 *
 * Auther:  杨则瑞
 * Encode:  utf-8 | CRLF
 * --------------------------------------
 */

const char * title = 
"====================================================================== \n"\
" WORK 3 of Chapter 2                                                   \n"\
"---------------------------------------------------------------------- \n"\
" Goal: Locate elements and increase the located elem's counter. Then,  \n"\
" rearange their positions so that elements will statisfy that          \n"\
" Elements with higher counter value is at position closer to the heaed.\n"\
"====================================================================== \n";


#include<stdio.h>
#include<dual_list.h>
#include<debuging.h>

typedef struct data_t
{
    long long frq;
    int key;

} data_t;

/**
 * 格式化输出表的内容到文件
 */
static void duList_data_t_to_file (const duList_t * self, FILE* fd);
static void duList_data_t_to_file_vartab (const duList_t * self, FILE* fd);


/**
 * 从文件格式化读入数据
 */
static void duList_data_t_from_file (duList_t * self, FILE* fd, int limt);


/**
 * 定位一个元素，当元素被找到时元素的计数器加１并将其向前移动到尽可能靠后的位置,且
 * 使得顺序遍历链表各个元素的计数器不减。
 */
int duList_data_t_locate(duList_t * self, int key, data_t *data_dest)
{
    duList_node_t * p = self->_header->next;

    long long freq = ((data_t *)(p->data))->frq;
    duList_node_t * pre_pos = p;

    while (1)
    {
        if(p == self->_header)
        {
            return 0;
        }

        if(((data_t *)(p->data))->frq < freq)
        {
            pre_pos = p;
            freq = ((data_t *)(p->data))->frq;
        }

        if(((data_t *)(p->data))->key == key)
        {
            ((data_t *)(p->data))->frq ++;

            if(((data_t *)(p->data))->frq > freq & p != pre_pos)
            {

                p->prev->next = p->next;
                p->next->prev = p->prev;

                pre_pos->prev->next = p;
                p->prev = pre_pos->prev;
                p->next = pre_pos;
                pre_pos->prev = p;

            }

            memcpy(data_dest,p->data,self->_elem_size);

            return 1;
        }

        p = p->next;
    }

}




#ifdef DESKTOP_MODE /*===========================================================*/
int main()
{
    duList_t d_list;
    duList_init(&d_list,sizeof(data_t));

    printf(title);

    printf("Pleae input the number of input (n)\n");

    int n;
    int qod = scanf("%d%*[^\n]", &n);

    if(qod != 1)
    {
        char errormsg[64];
        sprintf(errormsg,"Expect 1 integer but receive %d.\n", qod);
        _debug(errormsg,"ERROR");
        duList_uninit(&d_list);
        return -1;
    }

    if(n < 0)
    {
        _debug("Negative N","ERROR");
        duList_uninit(&d_list);
        return -1;
    }  

    if(n == 0)
    {
        printf("Note: n is 0, list will be empty\n");
    }


    if(n != 0)
    {
        printf("Please enter %d numbers to fill the array:\n", n);
    }

    duList_data_t_from_file(&d_list,stdin,n);

    printf("Done.\nPlease input queries(enter \"stop\" to stop querying):\n");

    while (1)    
    {
        data_t p;
        
        char query[124];
        int qod = scanf("%120s", & query);
        const char * cmd = "stop";
        int num;

        enum {
            notNumber = 0,
            number,
            invalid
        } typ; 

        typ = sscanf(query,"%d",&num);

        if(typ == 0){

            // 判断输入是不是stop
            for(int i = 0; i < 4; ++ i)
            {
                if(cmd[i] != query[i])
                {
                    typ = invalid;
                    break;
                }
            }

            if(typ == invalid)
            {
                _debug("Invalid input.","WARN");
                continue;
            }
            else
            {
                printf("Stopped.\n");
                break;
            }
        }


        if(qod != 1)
        {
            _debug("Invalid Input. You should enter integer or \"stop\"","ERROR");
        }

        printf("Finding: %d:",num);

        int s = duList_data_t_locate(&d_list,num,&p);
 
        if(s == 1)
        {
            printf("found %3d (%3d counted)\n", p.key, p.frq);
        }
        else
        {
            printf("found none\n", p.key, p.frq);
        }


        duList_data_t_to_file(&d_list,stdout);


        putchar('\n');
    }

    system("pause");

    //析构
    duList_uninit(&d_list);
    return 0;
}

#else 

int main()
{
    duList_t d_list;
    duList_init(&d_list,sizeof(data_t),NULL);

    int n, m;
    int qod = scanf("%d%d", &n, &m);

    if(qod != 2)
    {
        char errormsg[64];
        sprintf(errormsg,"Expect 2 integer but receive %d.\n", qod);
        _debug(errormsg,"ERROR");
        duList_uninit(&d_list);
        return -1;
    }

    if(n < 0 || m < 0)
    {
        _debug("Negative N or M","ERROR");
        duList_uninit(&d_list);
        return -1;
    }  


    duList_data_t_from_file(&d_list,stdin,n);

    for(int i = 0; i < m; ++ i)
    {
        data_t p;
        
        int query;
        int qod = scanf("%d", & query);

        if(qod != 1)
        {
            _debug("Invalid Query","ERROR");
        }

        int s = duList_data_t_locate(&d_list,query,&p);
 
 
    }


    duList_data_t_to_file_vartab (&d_list,stdout);

    putchar('\n');

    //析构
    duList_uninit(&d_list);
    return 0;
}

#endif /*========================================================================*/












// 辅助函数的实现 

static void duList_data_t_from_file (duList_t * self, FILE* fd, int limt)
{

    for(int i = 0; i < limt; ++ i)
    {
        data_t wd;
        
        int qod = fscanf(fd,"%d",&wd.key);

        if(qod != 1)
        {
            _debug("Invalid data: not a integer.\n Skipping it.","WARN");
            continue;
        }

        wd.frq = 0;

        duList_insert_reverse(self,0,&wd);
    }

    return;
}


static void duList_data_t_to_file (const duList_t * self, FILE* fd)
{
    size_t len = duList_length(self);
    duList_node_t *p = self->_header->next;
    int is_first = 1;

    fprintf(fd,"[");
    
    for(int i = 0; i < len; ++ i)
    {
        data_t data = *(data_t*)(p->data);
        if(is_first != 0)
        {
            fprintf(fd,"%d:fq.%d",data.key,data.frq);
            is_first = 0;
        }
        else
        {
            fprintf(fd,", %d:fq.%d",data.key,data.frq);
        }
        p = p->next;
    }
    
    fprintf(fd,"]");
    return;
}


static void duList_data_t_to_file_vartab (const duList_t * self, FILE* fd)
{
    size_t len = duList_length(self);
    duList_node_t *p = self->_header->next;

\
    
    for(int i = 0; i < len; ++ i)
    {
        data_t data = *(data_t*)(p->data);

        fprintf(fd,"%d %d\n",data.key,data.frq);
        
        p = p->next;
    }
    
    return;
}
